% Ejercicio "Sentencia if de C"
\subsection*{\fbox{\theejercicio} - Sentencia {\tt if} de C}

Para la gram\'atica:

\begin{center}
\begin{tabular}{|lcl|} \hline
                          &               &                                           \\
{\em Lista-de-Sentencias} & $\rightarrow$ & {\em Sentencia}                           \\
                          & $|$           & {\em Lista-de-Sentencias Sentencia}       \\
{\em Sentencia}           & $\rightarrow$ & {\em Expresi\'on} {\bf ;}                 \\
                          & $|$           & {\tt if} {\bf (} {\em Expresi\'on} {\bf )} {\em Sentencia}                            \\
                          & $|$           & {\tt if} {\bf (} {\em Expresi\'on} {\bf )} {\em Sentencia} {\tt else} {\em Sentencia} \\
                          & $|$           & {\bf (} {\em Lista-de-Sentencias} {\bf )} \\
{\em Exprei\'on}          & $\rightarrow$ & {\bf ENTERO}                              \\
                          & $|$           & {\bf IDENT}                               \\
                          & $|$           & {\em Expresi\'on} $==$ {\em Expresi\'on}  \\
                          & $|$           & {\bf (} {\em Expresi\'on} {\bf )}         \\
                          & $|$           & {\bf IDENT} $=$ {\em Expresi\'on}         \\
                          &               &                                           \\ \hline
\end{tabular}
\end{center}

\begin{enumerate}[1)]
\item Demostrar que esta gram\'atica no es LL(1).
\item Para la gram\'atica que se muestra en el enunciado construir los conjuntos de s\'{\i}mbolos directores para cada regla.
\item Construir las tablas de an\'alisis LL(1) para el lenguaje generado por esta gram\'atica, teniendo en cuenta que en caso de conflicto la palabra reservada {\tt else} debe ir asociada a la sentencia {\tt if} m\'as pr\'oxima, que el operador de comparaci\'on tiene menor prioridad de operaci\'on que el operador de asignaci\'on, y que todos los operadores son asociativos por la izquierda.
\end{enumerate}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

Apartado 1)

La gram\'atica es recursiva por la izquierda y por tanto no puede ser LL(1). V\'ease adem\'as el apartado c.

\medskip

Apartado 2)

\begin{center}
\begin{tabular}{|lcl|l|} \hline
                          &               &                                            & {\bf S\'{\i}mbolos directores}         \\ \hline
{\em Lista-de-Sentencias} & $\rightarrow$ & {\em Sentencia}                            & {\bf ENTERO IDENT (} {\tt if} {\bf \{} \\ \hline
                          & $|$           & {\em Lista-de-Sentencias Sentencia}        & {\bf ENTERO IDENT (} {\tt if} {\bf \{} \\ \hline
{\em Sentencia}           & $\rightarrow$ & {\em Expresi\'on} {\bf ;}                  & {\bf ENTERO IDENT (}                   \\ \hline
                          & $|$           & {\tt if} {\bf (} {\em Expresi\'on} {\bf )} {\em Sentencia}                            & {\tt if} \\ \hline
                          & $|$           & {\tt if} {\bf (} {\em Expresi\'on} {\bf )} {\em Sentencia} {\tt else} {\em Sentencia} & {\tt if} \\ \hline
                          & $|$           & {\bf (} {\em Lista-de-Sentencias} {\bf )}  & {\bf \{}                               \\ \hline
{\em Exprei\'on}          & $\rightarrow$ & {\bf ENTERO}                               & {\bf ENTERO}                           \\ \hline
                          & $|$           & {\bf IDENT}                                & {\bf IDENT}                            \\ \hline
                          & $|$           & {\em Expresi\'on} $==$ {\em Expresi\'on}   & {\bf ENTERO IDENT (}                   \\ \hline
                          & $|$           & {\bf (} {\em Expresi\'on} {\bf )}          & {\bf  (}                               \\ \hline
                          & $|$           & {\bf IDENT} $=$ {\em Expresi\'on}          & {\bf IDENT}                            \\ \hline
\end{tabular}
\end{center}

Apartado 3)

Puesto que la gram\'atica no es LL(1), habr\'{\i}a que encontrar una gram\'atica equivalente que cumpliera esta condici\'on. Sin embargo, para el lenguaje definido por la gram\'atica del enunciado, no existe ninguna otra gram\'atica capaz de generarlo que cumpla la condici\'on LL(1). No obstante, el enunciado restringe el lenguaje indicando la precedencia y asociatividad de los operadores y de la cl\'ausula {\tt else}. A partir de esta informaci\'on puede construirse la gram\'atica:

\begin{center}
\begin{tabular}{|llcl|} \hline
         &                            &               &                                             \\
{\tt 1}  & {\em Lista-de-Sentencias}  & $\rightarrow$ & {\em Sentencia Lista-de-Sentencias'}        \\
{\tt 2}  & {\em Lista-de-Sentencias'} & $\rightarrow$ & {\em Sentencia Lista-de-Sentencias}         \\
{\tt 3}  &                            & $|$           & $\varepsilon$                               \\
{\tt 4}  & {\em Sentencia}            & $\rightarrow$ & {\tt if} {\bf (} {\em Expresi\'on} {\bf )} {\em Sentencia Parte-else} \\
{\tt 5}  &                            & $|$           & {\em Expresi\'on} {\bf ;}                   \\
{\tt 6}  &                            & $|$           & {\bf \{} {\em Lista-de-Sentencias} {\bf \}} \\
{\tt 7}  & {\em Parte-else}           & $\rightarrow$ & {\tt else} {\em Sentencia}                  \\
{\tt 8}  &                            & $|$           & $\varepsilon$                               \\
{\tt 9}  & {\em Exprei\'on}           & $\rightarrow$ & {\em T\'ermino Expresi\'on'}                \\
{\tt 10} & {\em Exprei\'on'}          & $\rightarrow$ & $==$ {\em Expresi\'on'}                     \\
{\tt 11} &                            & $|$           & $\varepsilon$                               \\
{\tt 12} & {\em T\'ermino}            & $\rightarrow$ & {\bf IDENT} {\em T\'ermino'}                \\
{\tt 13} & {\em T\'ermino'}           & $\rightarrow$ & {\bf IDENT} {\em Factor}                    \\
{\tt 14} &                            & $|$           & $\varepsilon$                               \\
{\tt 15} & {\em Factor}               & $\rightarrow$ & {\bf ENTERO}                                \\
{\tt 16} &                            & $|$           & {\bf IDENT}                                 \\
{\tt 17} &                            & $|$           & {\bf (} {\em Expresi\'on} {\bf )}           \\
         &                            &               &                                             \\ \hline
\end{tabular}
\end{center}

Para esta gram\'atica se construye la tabla LL(1) que resulta ser:

\begin{center}
\begin{tabular}{|l|cccccccccccc|} \hline
                           & {\tt if} & {\tt else} & $==$ & {\bf IDENT} & {\bf ENTERO} & {\bf (} & {\bf )} & {\bf ;} & $=$  & {\bf \{} & {\bf \}} & {\bf \$} \\ \hline
{\em Lista-de-Sentencias}  & 1        &            &      & 1           &              &         &         &         &      &  1       &          &          \\
{\em Lista-de-Sentencias'} & 2        &            &      & 2           &              &         &         &         &      &  2       &          &  3       \\
{\em Sentencia}            & 4        &            &      & 5           &              &         &         &         &      &  6       &          &          \\
{\em Parte-else}           & 8        & 7 y 8      &      & 8           &              &         &         &         &      &  8       &          &  8       \\
{\em Exprei\'on}           &          &            &      & 9           &              &         &         &         &      &          &          &          \\
{\em Exprei\'on'}          &          &            & 10   &             &              &         &  11     &  11     &      &          &          &          \\
{\em T\'ermino}            &          &            &      & 12          &              &         &         &         &      &          &          &          \\
{\em T\'ermino'}           &          &            & 14   &             &              &         &  14     &  14     &  13  &          &          &          \\
{\em Factor}               &          &            &      & 15          & 16           &  17     &         &         &      &          &          &          \\ \hline
\end{tabular}
\end{center}

En esta tabla existe un conflicto en entre las reglas 7 y 8 correspondientes al antecedente {\em Parte-else}. Este conflicto viene dado por la ambig\"uedad de sentencias como:

\begin{center}\verb@if (a==b) if (c==d) x=1; else x=2; z=7; ...@\end{center}

que puede interpretarse sem\'anticamente equivalente a:

\begin{center}\verb@if (a==b) { if (c==d) x=1; else x=2; } z=7; ...@\end{center}

o bien como:

\begin{center}\verb@if (a==b) { if (c==d) x=1; } else x=2; z=7; ...@\end{center}

El reconocimiento de la sentencia original usando la tabla LL(1) y hasta llegar al token de la palabra reservada {\tt else} va construyendo el \'arbol sint\'actico:

% Imagen del árbol sintáctico
\begin{center}
\includegraphics[0cm,0cm][9.95cm,6.69cm]{./capitulo3/ejercicios/figuras/arbol_sintactico.jpg}
\end{center}

Esta situaci\'on corresponde al contenido de la pila de an\'alisis:

\begin{center}
\begin{tabular}{|c|}
                           \\
                           \\ \hline
{\em Parte-else}           \\ \hline
{\em Parte-else}           \\ \hline
{\em Lista-de-Sentencias'} \\ \hline
\end{tabular}
\end{center}

Dado que la palabra reservada {\tt else} debe asociarse a la sentencia {\tt if} m\'as pr\'oxima, en caso de que en la pila de reconocimiento se encuentre el s\'{\i}mbolo no terminal {\em Parte-else} y en la entrada el s\'{\i}mbolo terminal {\tt else}, debe realizarse la sustituci\'on de \'este seg\'un la regla (7), completando as\'{\i} el reconocimiento de la sentencia {\tt if} que di\'o origen a que el s\'{\i}mbolo no-terminal {\em Parte-else} entrase en la pila. De haber elegido la regla (8) el reconocimiento de la cadena de entrada dar\'{\i}a por terminado el an\'alisis de la sentencia {\tt if} leida recientemente. No hay ning\'un caso en que se produzca esta configuraci\'on que necesite la elecci\'on de la regla (8) para realizar un reconocimiento correcto. Por tanto la ambig\"uedad en el reconocimiento sint\'actico puede solucionarse eligiendo siempre la regla (7) en la casilla en la que aparece el conflicto.